require 'set'
require 'singleton'
require 'pp'
require 'rubygems'
require 'ruby_parser'

module RSense
  class ::Sexp
    def vertex
      @vertex ||= RSense.const_get(self[0].to_s.capitalize + 'Vertex').new(self)
    end

    def vertex=(other)
      @vertex = other
    end

    def deep_dup
      Sexp.new(*map {|c| c.instance_of?(Sexp) ? c.deep_dup : c})
    end
  end

  class TypeVariable < Set
    def to_s() "{#{to_a.join(', ')}}" end
    def inspect() to_s end
  end

  class Vertex
    attr_reader :node
    attr_accessor :type_var
    attr_reader :connections
    attr_reader :flows
    attr_accessor :propagate_tick

    def initialize(node)
      @node = node
      @type_var = TypeVariable.new
      @connections = Set.new
      @flows = Set.new
    end

    def connect(other)
      @connections << other
      other.propagated(self)
    end

    def flow(other)
      @flows << other
    end

    def propagated(other)
      @type_var += other.type_var
    end

    def type
      # TODO more efficient way
      type_var.size == 1 and type_var.find {|v| v}
    end

    def typed?() !type_var.empty? end
  end

  class ValueVertex < Vertex
    attr_reader :value

    def initialize(node, value, type)
      super(node)
      @value = value
      type.connect(self)
    end
  end

  class LitVertex < ValueVertex
  end

  class ArrayVertex < ValueVertex
  end

  class HashVertex < ValueVertex
  end

  class ElementVertex < Vertex
    def initialize(type_var)
      super(nil)
      @type_var = type_var
    end
  end

  class CdeclVertex < Vertex
    def name() @node[1] end
    def value() @node[2] end
  end

  class ConstVertex < Vertex
    def name() @node[1] end
  end

  class ModuleVertex < Vertex
    attr_accessor :cref
    attr_accessor :constants      # TODO hide
    attr_accessor :includes
    attr_writer :methods

    def initialize(node)
      super
      @constants = {}
      @methods = {}
      @includes = Set.new
      @type_var << self
    end

    def lookup_method(name)
      @methods[name]
    end

    def define_method(name, vertex)
      @methods[name] = vertex
    end

    def alias_method(new_name, old_name)
      @methods[new_name] = @methods[old_name]
    end

    def define_native_method(name, *args)
      meth = Sexp.new(:defn, name,
                      Sexp.new(:args, *args),
                      Sexp.new(:scope,
                               Sexp.new(:native, Proc.new))).vertex
      @methods[name] = meth
    end

    def sent(method)
      # method called
    end

    def methods(inherited_too = true)
      result = Set.new
      result += @methods.keys
      @includes.each do |include|
        result += include.methods(inherited_too)
      end
      result.to_a
    end

    def include(mod)
      @includes << mod.meta
    end

    def name() @node[1] end
    def body() @node[2] end

    def to_s() name.to_s end
    def inspect() to_s end
  end

  class ClassVertex < ModuleVertex
    attr_accessor :klass        # Class object
    attr_accessor :super_class
    attr_reader :instance_vars

    def initialize(node)
      super
      @klass = nil
      @instance_vars = {}
      @super_class = nil
    end

    def lookup_method(name)
      @includes.each do |mod|
        method = mod.lookup_method(name)
        return method if method
      end
      
      method = super(name)
      if !method and @super_class and self != @super_class
        method = @super_class.lookup_method(name)
      end
      method
    end

    def methods(inherited_too = true)
      result = Set.new(super)
      result += @super_class.methods(inherited_too) if @super_class and inherited_too
      result.to_a
    end

    def instantiate
      inst = ClassVertex.new(@node)
      inst.klass = @klass
      inst.super_class = @super_class
      inst.cref = @cref
      inst.constants = @cref
      inst.includes = @includes
      inst.methods = @methods
      inst
    end

    def name() @node[1] end
    def body() @node[3] end
    def super_name() @node[2] end

    def to_s() name.to_s end
    def inspect() to_s end
  end

  class ClassObjectVertex < ModuleVertex
    attr_accessor :klass
    attr_reader :meta

    def initialize(klass, meta)
      super(nil)
      @klass = klass
      @meta = meta
    end

    def lookup_method(name)
      @includes.each do |mod|
        method = mod.klass.lookup_method(name)
        return method if method
      end

      method = super(name)
      if !method and @meta.instance_of?(ClassVertex)
        super_class = @meta.super_class
        if super_class and super_class.klass and @meta != super_class
          method = super_class.klass.lookup_method(name)
        end
      end

      method = @klass.lookup_method(name) unless method

      method
    end

    def methods(inherited_too = true)
      super + @klass.methods(inherited_too)
    end

    def to_s() meta.to_s end
    def inspect() to_s end
  end

  class DefnVertex < Vertex
    attr_accessor :cref
    attr_accessor :scope
    attr_accessor :processed
    attr_reader :templates

    def initialize(node)
      super
      @templates = {}
      @processed = false
    end

    def name() @node[1] end
    def args() @node[2][1..-1] end
    def body() @node[3][1] end

    def arity() args.size end

    def native?
      body[0] == :native
    end
  end

  class DefsVertex < DefnVertex
    def base() @node[1] end
    def name() @node[2] end
    def args() @node[3][1..-1] end
    def body() @node[4][1] end
  end

  class GvarVertex < Vertex
    def name() node[1] end
  end

  class GasgnVertex < Vertex
    def name() node[1] end
    def value() node[2] end
  end

  class IvarVertex < Vertex
    def name() @node[1] end
  end

  class IasgnVertex < Vertex
    def name() @node[1] end
    def value() @node[2] end
  end

  class LvarVertex < Vertex
    def name() @node[1] end
  end

  class LasgnVertex < Vertex
    def name() @node[1] end
    def value() @node[2] end
  end

  class MasgnVertex < Vertex
    def name() @node[1] end
    def value() @node[2] end
  end

  class OrVertex < Vertex
    def left() @node[1] end
    def right() @node[2] end
  end

  class Op_asgn_orVertex < Vertex
    def value() @node[2] end
  end

  class AndVertex < Vertex
    def left() @node[1] end
    def right() @node[2] end
  end

  class IfVertex < Vertex
    def condition() @node[1] end
    def then_clause() @node[2] end
    def else_clause() @node[3] end
  end

  class ReturnVertex < Vertex
    def value() @node[1] end
  end

  class VariableVertex < Vertex
    attr_reader :name
    
    def initialize(name)
      super(nil)
      @name = name
    end

    def to_s() @name.to_s end
    def inspect() to_s end
  end

  class CallVertex < Vertex
    attr_accessor :block
    
    def receiver() @node[1] end
    def selector() @node[2] end
    def args() @node[3][1..-1] end
  end

  class SuperVertex < Vertex
    def block() nil end
    def args() @node[1..-1] end
  end

  class ZsuperVertex < Vertex
    def block() nil end
  end

  class AttrasgnVertex < CallVertex
  end

  class Colon2Vertex < Vertex
    def base() @node[1] end
    def name() @node[2] end
  end

  class Colon3Vertex < Vertex
    def name() @node[1] end
  end

  class SplatVertex < Vertex
    def value() @node[1] end
  end

  class IterVertex < Vertex
    def call() @node[1] end
    def args() @node[2] end
    def body() @node[3] end
  end

  class YieldVertex < Vertex
    def args() @node[1..-1] end
  end

  class Block_passVertex < Vertex
    def value() @node[1] end
  end

  class BlockVertex < Vertex # This is not for Ruby's block
  end

  class Frame
    attr_reader :value
    attr_reader :parent

    def initialize(value, parent = nil)
      @value = value
      @parent = parent
    end
  end

  class ClassRef < Frame
  end

  class Scope
    attr_reader :local_vars

    def initialize
      @local_vars = {}
    end

    def clear
      @local_vars.clear
    end
  end

  class Block
    attr_reader :node
    attr_reader :cref
    attr_reader :scope
    attr_reader :parent
    
    def initialize(node, cref, scope, parent)
      @node = node
      @cref = cref
      @scope = scope
      @parent = parent
    end

    def hash() @node.hash end
    def eql?(other) @node.eql?(other) end

    def deep_dup
      Block.new(@node.deep_dup, @cref, @scope, @parent)
    end
  end

  class TemplateId
    attr_reader :receiver, :args, :block
    
    def initialize(receiver, args, block)
      @receiver = receiver
      @args = args
      @block = block
    end
    
    def hash
      @receiver.hash ^ @args.hash ^ @block.hash
    end
    
    def eql?(other)
      @receiver.equal?(other.receiver) and @args.eql?(other.args) and @block.equal?(other.block)
    end
  end
  
  class Inferrer
    def initialize
      @scope = Scope.new
      @body = nil
      @block = nil
      @propagate_tick = 0
      @flow = nil
      @given_block = nil
      @call_table = Hash.new(0)
      @global_vars = {}
      @features = {}
      @load_path = $LOAD_PATH.dup
      @current_method = nil
      @current_method_args = nil
      @current_method_arg_vertecies = nil
      @call_handlers = []
      define_kernel
      prologue
    end

    def add_call_handler(handler)
      @call_handlers << handler
    end

    def find(name)
      @load_path.each do |lib|
        path = "#{lib}/#{name}.rb"
        return path if File.file?(path)
      end
    end

    def clear
      @scope.clear
    end

    def infer(source)
      ast = RubyParser.new.parse(source)
      process(ast)
      ast
    end

    def process(node)
      meth = "process_#{node[0]}"
      return process_body(node) unless respond_to?(meth)
      send(meth, node)
    end

    def process_cdecl(node)
      v = node.vertex
      result = process(v.value)
      if result
        result.connect(v)
        @cref.value.constants[v.name] = result
      end
      @result = v
    end

    def process_cvdecl(node)
      # TODO
      @result = nil
    end

    def process_const(node)
      v = node.vertex
      const = lookup_const(@cref, v.name)
      const.connect(v) if const
      @result = v
    end

    def process_module(node)
      v = node.vertex
      object = @cref.value.constants[v.name]
      if object
        @cref = object.meta.cref
      else
        object = ClassObjectVertex.new(@Module, v)
        @cref.value.constants[v.name] = object
        v.cref = @cref = ClassRef.new(v, @cref)
      end
      @self, old_self = object, @self
      process(v.body)
      @self = old_self
      @cref = @cref.parent
      @result = nil
    end

    def process_class(node)
      v = node.vertex
      object = @cref.value.constants[v.name]
      old_cref = @cref
      if object
        @cref = object.meta.cref
      else
        object = ClassObjectVertex.new(@Class, v)
        @cref.value.constants[v.name] = object
        v.klass = object
        # TODO process(v.super_name)...
        if v.super_name
          super_name = v.super_name[1] if v.super_name[1].instance_of?(Symbol)
        else
          super_name = :Object if v.name != :Object
        end
        if super_name
          super_class = lookup_const(@cref, super_name)
          v.super_class = super_class.meta if super_class
        end
        v.cref = @cref = ClassRef.new(v, @cref)
      end
      @self, old_self = object, @self
      process(v.body)
      @self = old_self
      @cref = old_cref
      @result = nil
    end

    def process_sclass(node)
      # TODO
      @result = nil
    end

    def process_defn(node)
      v = node.vertex
      @cref.value.define_method(v.name, v)
      v.cref = @cref
      @result = nil
    end

    def process_defs(node)
      # TODO singleton method?
      v = node.vertex
      base = process(v.base)
      if base and base.type.instance_of?(ClassObjectVertex)
        base.type.define_method(v.name, v)
        v.cref = @cref          # TODO?
      end
      @result = nil
    end

    def process_gvar(node)
      v = node.vertex
      var = @global_vars[v.name]
      if var
        var.connect(v)
        propagate(v)
      else
        var = VariableVertex.new(v.name)
        @global_vars[v.name] = var
        var.connect(v)
      end
      @result = v
    end

    def process_gasgn(node)
      v = node.vertex
      value = v.value ? process(v.value) : @default_value
      var = local_var(v.name)
      unless var
        var = VariableVertex.new(v.name)
        @global_vars[v.name] = var
      end
      value.connect(var)
      var.connect(v)
      propagate(var)
      @result = v
    end

    def process_ivar(node)
      v = node.vertex
      name = v.name
      if @self.instance_of?(ClassVertex)
        var = @self.instance_vars[name]
        if var
          var.connect(v)
          propagate(var)
          return @result = v
        end

        # not found
        var = VariableVertex.new(name)
        @self.instance_vars[name] = var
        var.connect(v)
      end
      @result = v
    end

    def process_iasgn(node)
      v = node.vertex
      name = v.name
      process(v.value)
      if @self.instance_of?(ClassVertex)
        var = @self.instance_vars[name]
        if var
          v.value.vertex.connect(var)
          var.connect(v)
          propagate(var)
          return @result = v
        end

        # not found
        var = VariableVertex.new(name)
        @self.instance_vars[name] = var
        v.value.vertex.connect(var)
        var.connect(v)
      end
      @result = v
    end

    def process_array(node)
      # TODO connect array type
      value = []
      node[1..-1].each do |val|
        val = process(val)
        value << val
      end
      @result = node.vertex = ArrayVertex.new(node, value, make_typed_array_type(value))
    end

    def process_hash(node)
      # TODO connect
      value = {}
      1.step(node.size - 2, 2) do |i|
        key = node[i]
        val = node[i + 1]
        key = process(key)
        val = process(val)
        value[key] = val if key and val
      end
      @result = node.vertex = HashVertex.new(node, value, make_typed_hash_type(value))
    end

    def process_dregx(node)
      # TODO
      @result = node.vertex = @Regexp
    end

    def process_dregx_once(node)
      # TODO
      @result = node.vertex = @Regexp
    end

    def process_lit(node)
      value = node[1]
      name = value.class.name
      klass = lookup_const(@cref, name.intern)
      raise "Undefined builtin class #{name}" unless klass
      node.vertex = LitVertex.new(node, value, klass.meta)
      @result = node.vertex
    end

    def process_str(node)
      process_lit(node)
    end

    def process_evstr(node)
      # TODO prologue
      @result = node.vertex = @String
    end

    def process_dstr(node)
      # TODO prologue
      @result = node.vertex = @String
    end

    def process_true(node)
      # TODO prologue
      @result = node.vertex = @TrueClass
    end

    def process_false(node)
      # TODO prologue
      @result = node.vertex = @FalseClass
    end

    def process_undef(node)
      # TODO?
      @result = nil
    end

    def process_alias(node)
      # support only literal representation
      if node[1] and node[1][0] == :lit and node[2] and node[2][0] == :lit
        new_name = node[1][1]
        old_name = node[2][1]

        # method
        @cref.value.alias_method(new_name, old_name)

        # TODO gvar
      end
      @result = nil
    end

    def process_valias(node)
      # TODO
      @result = nil
    end

    def process_defined(node)
      # TODO?
      @result = nil
    end

    def process_nil(node)
      process_lit(node)
    end

    def process_self(node)
      # TODO
      @result = node.vertex = @self
    end

    def process_call(node)
      v = node.vertex
      if v.receiver
        result = process(v.receiver)
        result.flow(v) if result
      elsif @self
        @self.flow(v)
      end
      v.args.each do |arg|
        result = process(arg)
        result.flow(v) if result
      end
      @result = do_call(v)
    end

    def process_super(node)
      # TODO no need to recalculate cartesian product
      # TODO connect?
      v = node.vertex
      args = v.args
      args.each do |arg|
        result = process(arg)
        result.flow(v) if result
      end
      method = @current_method
      if method and callable?(@self, args)
        process_zsuper(node, method, expand_call_arguments(method, args))
      end
      @result = v
    end

    def process_zsuper(node, method = nil, args = nil)
      # TODO no need to recalculate cartesian product
      # TODO connect?
      v = node.vertex
      method ||= @current_method
      args ||= @current_method_args
      if method and args
        cref = method.cref
        name = method.name
        method = nil
        if cref
          klass = cref.value
          super_class = klass.super_class
          if super_class
            if @self.instance_of?(ClassObjectVertex)
              # lookup singleton method
              method = super_class.klass.lookup_method(name)
            else
              # lookup instance method
              method = super_class.lookup_method(name)
            end
          end
          method = klass.klass.lookup_method(name) unless method
          do_call_internal(v, method, @self, args) if method
        end
      end
      @result = v
    end

    def process_attrasgn(node)
      process_call(node)
    end

    def process_iter(node)
      v = node.vertex
      callv = v.call.vertex
      callv.block = Block.new(node, @cref, @scope, @given_block)
      callv.connect(v)
      process_call(v.call)
      @result = v
    end

    def process_yield(node)
      v = node.vertex
      if @given_block
        # TODO 1.9
        # TODO flow
        # TODO yield in block
        args = []
        v.args.each do |arg|
          arg = process(arg)
          # TODO flow
          # arg.flow(v)
          args << arg
        end
        body = do_yield(args)
        body.connect(v) if body
      end
      @result = v
    end

    def process_block_pass(node)
      # TODO
      @result = node.vertex
    end

    def process_native(node)
      @result = node[1].call
    end

    def process_colon2(node)
      v = node.vertex
      base = process(v.base)
      if base and base.type.instance_of?(ClassObjectVertex)
        const = lookup_const(base.type.meta.cref, v.name)
        const.connect(v) if const
      end
      @result = v
    end

    def process_colon3(node)
      @result = node.vertex
    end

    def process_if(node)
      v = node.vertex
      process_then = true
      process_else = true
      process(v.condition)
      if @result and @result.type == @TrueClass
        process_else = false
      elsif @result and @result.type == @FalseClass
        process_then = false
        @result = nil
      else
        @result = nil
      end

      if process_then and v.then_clause
        process(v.then_clause)
        @result.connect(v) if @result
      end

      if process_else and v.else_clause
        process(v.else_clause)
        @result.connect(v) if @result
      end

      @result = v
    end

    def process_for(node)
      # TODO
      @result = nil
    end

    def process_while(node)
      # TODO
      @result = nil
    end

    def process_when(node)
      # TODO
      @result = nil
    end

    def process_unless(node)
      # TODO
      @result = nil
    end

    def process_case(node)
      # TODO
      @result = nil
    end

    def process_next(node)
      # TODO
      @result = nil
    end

    def process_break(node)
      # TODO
      @result = nil
    end

    def process_return(node)
      v = node.vertex
      process(v.value).connect(v) if v.value
      v.connect(@body) if @body
      @result = v
    end

    def process_lvar(node)
      v = node.vertex
      var = local_var(v.name)
      if var                    # must be found?
        var.connect(v)
        propagate(v)
      end
      @result = v
    end

    def process_lasgn(node)
      v = node.vertex
      if v.value
        value = process(v.value)
      elsif @default_value
        value = @default_value
        value = value[0] if value.instance_of?(Array) # XXX
      end
      var = local_var(v.name)
      unless var
        var = VariableVertex.new(v.name)
        @scope.local_vars[v.name] = var
      end
      if value
        value.connect(var)
        value.connect(v)
        # TODO need to propagate?
        #var.connect(v)
        #propagate(var)
      end
      @result = v
    end

    def process_masgn(node)
      v = node.vertex
      elem_value = nil
      if v.value
        value = process(v.value)
        if value.value
          # value array
          value = value.value
        elsif value.respond_to?(:elem_type_var)
          # typed array
          elem_value = ElementVertex.new(value.elem_type_var)
        end
      else
        value = @default_value
      end
      names = v.name
      1.upto(names.size) do |i|
        @default_value = elem_value || value[i - 1]
        name = names[i]
        process(name) if name and @default_value
      end
      @default_value = nil
      @result = nil
    end

    def process_splat(node)
      v = node.vertex
      result = process(v.value)
      result.connect(v) if result
      @result = v
    end

    def process_to_ary(node)
      # TODO connect?
      value = nil
      result = process(node[1])
      if result
        result.type_var.each do |type|
          if type.respond_to?(:elem_type_var) and value.nil?
            value = type.value
            value = Set.new(type.elem_type_var) unless value
          else
            value = Set.new unless value.instance_of?(Set)
            value << type
          end
        end
        return @result = make_typed_array_type(value)
      end
      @result = nil
    end

    def process_not(node)
      # TODO boolean?
      @result = process(node[1])
    end

    def process_or(node)
      v = node.vertex
      if v.left
        process(v.left)
        @result.connect(v) if @result
      end
      if v.right
        process(v.right)
        @result.connect(v) if @result
      end
      @result = v
    end
    
    def process_op_asgn_or(node)
      v = node.vertex
      process_body(node)
      v.value.vertex.connect(v)
      @result = v
    end

    def process_and(node)
      process_or(node)
    end

    def process_match3(node)
      # TODO
      @result = nil
    end

    def process_scope(node)
      body = node[1]
      @result = nil
      if body
        @scope, old_scope = Scope.new, @scope
        @result = process(body)
        @scope = old_scope
      end
      @result
    end

    def process_resbody(node)
      p node
    end

    def process_block(node)
      # This is not Ruby's body
      old_body = @body
      @body = node.vertex
      process_body(node)
      @result.connect(@body) if @result
      @result = @body
      @body = old_body
    end

    def process_body(node)
      node.each do |child|
        @result = process(child) if child.instance_of?(Sexp)
      end
      node.vertex
    end

    def propagate(vertex, tick = nil)
      tick = @propagate_tick += 1 unless tick
      return if vertex.propagate_tick == tick
      vertex.propagate_tick = tick
      vertex.connections.each do |con|
        con.propagated(vertex)
        propagate(con, tick)
      end

      unless @flow
        @flow = true
        vertex.flows.each do |flow|
          if flow.instance_of?(CallVertex)
            do_call(flow)
          elsif flow.instance_of?(SuperVertex)
            # TODO
          end
        end
        @flow = false
      end
    end

    def define_attr_reader(name)
      process_defn(Sexp.new(:defn, name,
                            Sexp.new(:args),
                            Sexp.new(:scope,
                                     Sexp.new(:block,
                                              Sexp.new(:ivar, ('@' + name.to_s).intern)))))
    end

    def define_attr_writer(name)
      process_defn(Sexp.new(:defn, (name.to_s + '=').intern,
                            Sexp.new(:args, name),
                            Sexp.new(:scope,
                                     Sexp.new(:block,
                                              Sexp.new(:iasgn,
                                                       ('@' + name.to_s).intern,
                                                       Sexp.new(:lvar, name))))))
    end

    def lookup_const(cref, name)
      cref.value.includes.each do |mod|
        const = mod.constants[name]
        return const if const
      end

      c = cref
      while c
        const = c.value.constants[name]
        return const if const
        c = c.parent
      end

      # not found in cref. then search superclasses
      klass = cref.value
      if klass.instance_of?(ClassVertex)
        while super_class = klass.super_class and klass != super_class
          const = super_class.constants[name]
          return const if const
          klass = super_class
        end
      end
    end

    def local_var(name)
      @scope.local_vars[name]
    end

    def local_var_type(name)
      var = local_var(name)
      var.type if var
    end

    def local_var_type_meta(name)
      type = local_var_type(name)
      type.meta if type
    end

    def local_var_value(name)
      var = local_var(name)
      var.value if var.instance_of?(ValueVertex)
    end

    def template(method, receiver, args, block, force = false)
      id = TemplateId.new(receiver, args, block)
      tmpl = method.templates[id]
      return tmpl if tmpl and !tmpl.native? and !force
      tmpl = method.node.deep_dup.vertex
      method.templates[id] = tmpl unless force
      tmpl.cref = method.cref || @cref
      tmpl.scope = @scope
      method.args.each_with_index do |arg, i|
        if arg.instance_of?(Symbol)
          if arg.to_s[0] == ?*
            # rest
            arg = arg.to_s[1..-1].intern
            var = VariableVertex.new(arg)
            value = []
            i.upto(args.length - 1) do |j|
              value << args[j] if args[j]
            end
            var.type_var << make_typed_array_type(value)
          else
            var = VariableVertex.new(arg)
            var.type_var << args[i] if args[i]
          end
          @scope.local_vars[arg] = var
        else
          # TODO override?
          # maybe default arguments expression
          process(arg)
        end
      end
      tmpl
    end

    def callable?(receiver, args)
      # TODO
      # Maybe we should call functions even if receiver and args are not typed.
      receiver.typed? and args.all? {|arg| arg.vertex.typed?}
    end

    def expand_call_arguments(method, args)
      result = []
      args.each_with_index do |arg, i|
        argv = arg.vertex
        if argv.instance_of?(SplatVertex)
          type = argv.type
          if type.respond_to?(:elem_type_var)
            if type.value
              result += type.value.map {|v| v.type_var}
            else
              elem_types = type.elem_type_var
              i.upto(method.arity - 1) {|j| result << elem_types}
            end
          end
        else
          result << argv.type_var
        end
      end
      result
    end
    
    def do_call_internal(vertex, method, receiver, args)
      @current_method, old_current_method = method, @current_method
      @current_method_args, old_current_method_args = args, @current_method_args
      result = nil
      product = cartesian_product(args.map {|arg| arg.to_a})
      product.each do |args|
        @self, old_self = receiver, @self
        @cref, old_cref = method.cref || @cref, @cref
        @scope, old_scope = Scope.new, @scope
        old_block = @block
        @given_block, old_given_block = (vertex && vertex.block), @given_block
        tmpl = template(method, receiver, args, @given_block, @call_table[method] == 1)
        if !tmpl.processed or tmpl.native?
          @call_table[method] += 1
          tmpl.processed = true
          receiver.sent(method) if receiver
          result = process(tmpl.body)
          vertex.type_var += result.type_var if vertex and result
          @call_table[method] -= 1
        end
        @given_block = old_given_block
        @block = old_block
        @scope = old_scope
        @cref = old_cref
        @self = old_self
        if vertex
          tmpl.body.vertex.connect(vertex) unless tmpl.native?
          propagate(vertex)
        end
      end
      @current_method_args = old_current_method_args
      @current_method = old_current_method
    end

    def do_call(vertex)
      receiver = vertex.receiver ? vertex.receiver.vertex : @self
      return unless receiver
      if callable?(receiver, vertex.args)
        receivers = receiver.type_var
        receivers.each do |receiver|
          # call handlers first
          @call_handlers.each do |handler|
            handler.call(receiver, vertex.selector)
          end

          method = receiver.lookup_method(vertex.selector)
          @current_method_arg_vertecies, old_current_method_arg_vertecies = vertex.args, @current_method_arg_vertecies
          do_call_internal(vertex, method, receiver, expand_call_arguments(method, vertex.args)) if method
          @current_method_arg_vertecies = old_current_method_arg_vertecies
        end
      end
      vertex
    end

    def do_yield(args)
      old_given_block = @given_block
      block = @given_block.deep_dup
      @result = nil
      @default_value = args
      @cref, old_cref = block.cref, @cref
      @scope, old_scope = block.scope, @scope
      blk = block.node.vertex
      @default_value = @default_value[0] if @default_value.size == 1
      process(blk.args) if blk.args
      @given_block = @given_block.parent
      @result = process(blk.body) if blk.body
      @given_block = old_given_block
      @scope = old_scope
      @cref = old_cref
      @result
    end

    def make_typed_array_type(value)
      type = @Array.instantiate
      class << type
        attr_accessor :value
        attr_accessor :elem_type_var

        def sent(method)
          # value become not available once sent.
          @value = nil
        end
        
        def to_s() "Array#{@elem_type_var}" end
      end
      type_var = TypeVariable.new
      value.each {|v| type_var += v.type_var}
      type.value = value if value.instance_of?(Array)       # TODO propagate?
      type.elem_type_var = type_var
      type
    end

    def make_typed_hash_type(value)
      type = @Hash.instantiate
      class << type
        attr_accessor :value
        attr_accessor :key_type_var
        attr_accessor :value_type_var

        def sent(method)
          # lose value information
          @value = nil
        end

        def to_s() "Hash(#{@key_type_var}=>#{@value_type_var})" end
      end
      key_type_var = TypeVariable.new
      value_type_var = TypeVariable.new
      value.each do |key, value|
        key_type_var += key.type_var
        value_type_var += value.type_var
      end
      type.value = value if value.instance_of?(Hash)
      type.key_type_var = key_type_var
      type.value_type_var = value_type_var
      type
    end

    def make_kernel_class(name)
      ClassVertex.new(Sexp.new(:class, name))
    end

    def define_kernel
      @Class = make_kernel_class(:Class)
      @Object = make_kernel_class(:Object)
      @Module = make_kernel_class(:Module)

      @Module.super_class = @Object
      @Class.super_class = @Module

      @self = @Object
      @cref = ClassRef.new(@self)

      @Object.cref = @cref
      @Module.cref = @cref
      @Class.cref = @cref

      constants = @self.constants
      constants[:Object] = @Object.klass = ClassObjectVertex.new(@Class, @Object)
      constants[:Module] = @Module.klass = ClassObjectVertex.new(@Class, @Module)
      constants[:Class]  = @Class.klass = ClassObjectVertex.new(@Class, @Class)

      # define native methods
      @Object.define_native_method(:instance_of?, :other) do
        left = @self.type
        right = local_var_type_meta(:other)
        (left.instance_of?(ClassVertex) and right.instance_of?(ClassVertex) and left.name == right.name) ? @TrueClass : @FalseClass
      end

      @Object.define_native_method(:class) do
        @self.klass
      end
      
      @Class.define_native_method(:new, :'*args') do
        # TODO strong array
        if @self.respond_to?(:meta)
          new_self = @self.meta.instantiate
          initialize = new_self.lookup_method(:initialize)
          args = []
          args_type = local_var_type(:args)
          if initialize and args_type and args_type.respond_to?(:elem_type_var)
            if args_type.value
              args = args_type.value.map {|v| v.type_var}
            else
              initialize.args.size.times {args << args_type.elem_type_var}
            end
          end
          do_call_internal(nil, initialize, new_self, args) if initialize
          new_self
        end
      end

      @Module.define_native_method(:include, :name) do
        mod = local_var_type(:name)
        if mod and @self.instance_of?(ClassObjectVertex)
          @self.meta.include(mod)
        end
        nil
      end

      @Module.define_native_method(:attr) do
        if @current_method_arg_vertecies
          name = @current_method_arg_vertecies[0]
          define_attr_reader(name[1]) if name[0] == :lit
          # TODO writer
        end
        nil
      end

      @Module.define_native_method(:attr_reader) do
        if @current_method_arg_vertecies
          @current_method_arg_vertecies.each do |name|
            define_attr_reader(name[1]) if name[1].instance_of?(Symbol)
          end
        end
        nil
      end

      @Module.define_native_method(:attr_writer) do
        if @current_method_arg_vertecies
          @current_method_arg_vertecies.each do |name|
            define_attr_writer(name[1]) if name[1].instance_of?(Symbol)
          end
        end
        nil
      end

      @Module.define_native_method(:attr_accessor) do
        if @current_method_arg_vertecies
          @current_method_arg_vertecies.each do |name|
            if name[1].instance_of?(Symbol)
              define_attr_reader(name[1])
              define_attr_writer(name[1])
            end
          end
        end
        nil
      end
    end

    def prologue
      infer(<<-BUILTINS)
      class TrueClass
      end
       
      class FalseClass
      end

      class NilClass
      end

      class Numeric
        def +() self end
        def -() self end
        def ==(other) Boolean end
        def abs() self end
        def ceil() 0 end
        def floor() 0 end
        def round() 0 end
        def truncate() 0 end
        def coerce(number) [number, self] end
        def div(other) 0 end
        def quo(other)
          return 0.0
          return Rational(0, 1)
        end
        def divmod(other) [div(other), modulo(other)] end
        def integer?() self.instance_of?(Fixnum) end
        def module(other)
          return 0
          return 0.0
        end
        def nonzero?() self end
        def to_int() to_i end
        def zero?() Boolean end
        def step(limit, step = 1) yield self + step end
      end
       
      class Integer < Numeric
        def self.induced_from(num) 0 end

        def [](nth) 0 end
        def +(other) self end
        def -(other) self end
        def *(other) self end
        def /(other) self end
        def %(other) self end
        def **(other) self end
        def <=>(other) Bolean end
        def ==(other) Boolean end
        def <(other) Boolean end
        def <=(other) Boolean end
        def >(other) Boolean end
        def >=(other) Boolean end
        def ~() self end
        def |(other) self end
        def &(other) self end
        def ^(other) self end
        def <<(bits) self end
        def >>(bits) self end
        def chr() '' end
        def downto(min) yield self end
        def next() self end
        def succ() self end
        def times()
          yield self
          self
        end
        def to_int() self end
        alias :to_int :to_i
        def size() 0 end
        def to_f() 0.0 end
        def to_s(base = nil) '' end
        def upto(max)
          yield self
          self
        end
      end
       
      class Fixnum < Integer
        def +(other) other.instance_of?(Float) ? other : self end
        def -(other) +(other) end
        def *(other) +(other) end
        def /(other) +(other) end
        def %(other) +(other) end
        def id2name() '' end
        def to_sym() :a end
      end
       
      class Bignum < Fixnum
      end

      module Precision
        def prec(klass) self end
        def prec_i() 0 end
        def prec_f() 0.0 end
      end
       
      class Float < Numeric
        DIG = 0
        EPSILON = 0.0
        MANT_DIG = 0
        MAX = 0.0
        MIN = 0.0
        MAX_10_EXP = 0
        MIN_10_EXP = 0
        RADIX = 0
        ROUNDS = 0

        include Precision

        def self.induced_from(num) 0.0 end

        def +(other) self end
        def -(other) self end
        def *(other) self end
        def /(other) self end
        def %(other) self end
        def **(other) self end
        def <=>(other) Bolean end
        def ==(other) Boolean end
        def <(other) Boolean end
        def <=(other) Boolean end
        def >(other) Boolean end
        def >=(other) Boolean end
        def finite?() Boolean end
        def infinite?() Boolean end
        def nan?() Boolean end
        def to_f() self end
        def to_i() 0 end
        def truncate() 0 end
      end

      class String
      end

      class Symbol
      end

      class Regexp
      end
       
      module Enumerable
        def all?()
          each {|v| yield v}
          Boolean
        end

        alias :any? :all?

        def map
          result = []
          each {|v| x = yield v; result << x}
          result
        end

        alias :collect :map

        def each_with_index
          each {|v| yield v, 0}
          self
        end

        def find(ifnone = nil)
          result = nil
          each {|v| result = v; yield v}
          result
        end

        alias :detect :find

        def find_all(ifnone = nil)
          each {|v| yield v}
          self
        end

        alias :select :find_all

        alias :grep :select

        def inject(init = nil)
          each {|v| init = yield ((init || v), v)}
          init
        end

        def member?(val) Boolean end
        def include?(val) Boolean end

        def max
          # TODO
          result = nil
          each {|v| result = v; yield v, v}
          result
        end

        alias :max_by :max
        alias :min :max
        alias :min_by :max_by

        def partition
          a = []
          each {|v| a << v}
          [a]
        end

        alias :reject :find_all

        def sort
          each {|v| yield v, v}
          self
        end

        alias :sort_by :sort

        def to_a
          result = []
          each {|v| yield v; result << v}
          result
        end

        alias :entries :to_a

        def zip
          # TODO
          self
        end
      end

      module Comparable
        def ===(other) Boolean end
        def >(other) Boolean end
        def >=(other) Boolean end
        def <(other) Boolean end
        def <=(other) Boolean end
        def between?(min, max) Boolean end
      end

      class Range
        # TODO
      end

      class Array
        include Enumerable

        def self.[](*item)
          item.each {|v| push(v)}
          self
        end

        def []=(start, length, val)
          if val.nil?
            push(length)
            length
          else
            push(val)
            val
          end
        end
        # TODO +, *, etc
        def +(other) self end
        def *(times) self end
        def -(other) self end
        def &(other) self end
        def |(other) self end
        def <=>(other) 0 end
        def ==(other) Boolean end
        def assoc(key) self[0] end
        def at(pos) self[0] end
        def clear() self end
        # TODO collect!
        def each() yield self[0] end
        alias :collect! :collect
        alias :map! :map
        def compact() self end
        def compact!() self end
        # TODO
        def concat(other) self end
        def delete(val) val end
        def delete_at(pos) self[0] end
        def delete_if
          return yield self[0]
          self
        end
        alias :reject! :delete_if
        def each_index
          yield 0
          self
        end
        def empty?() Boolean end
        def fetch(nth, ifnone = nil)
          return yield nth
          self[nth]
        end
        # TODO
        def fill() self end
        def first(n = nil) n.nil? ? self : self[0] end
        def flatten() self end
        alias :flatten! :flatten
        def include?(val) Boolean end
        def index(val)
          yield 0
          0
        end
        def indexes(*index) self end
        def insert(nth, *val) self end
        def join(sep = $,) '' end
        def last(n = nil) n.nil? ? self : self[0] end
        def length() 0 end
        def size() 0 end
        def nitems() 0 end
        def pack(template) '' end
        def pop() self[0] end
        def push(*obj)
          obj.each {|v| self << v}
          self
        end
        def rassoc(obj) self[0] end
        def replace(another) self end
        def reverse() self end
        alias :reverse! :reverse
        def reverse_each
          each {|v| yield v}
          self
        end
        def rindex(val)
          yield 0
          0
        end
        def shift() self[0] end
        alias :slice :[]
        alias :slice! :[]
        alias :sort! :sort
        def to_a() self end
        alias :to_ary :to_a
        # TODO
        def transpose() self end
        def uniq() self end
        alias :uniq! :uniq
        alias :unshift :push
        def values_at(*index) self end
      end

      class Hash
        include Enumerable

        # TODO [item,value,...]
        def self.[](hash) 
          result = {}
          hash.each {|k, v| result[k] = v}
          result
        end

        def store(key, value) self[key] = value end
        def clear() self end
        # TODO default*
        def default(key = nil) nil end
        def default=(value) nil end
        def default_proc() nil end
        def delete(key)
          return yield key
          return self[key]
        end
        def reject
          each {|k, v| yield k, v}
          self
        end
        def delete_if
          ecah {|k, v| yield k, v}
          self
        end
        alias :reject! :delete_if
        alias :each_pair :each
        def each_key
          yield key
          self
        end
        def each_value
          yield self[nil]
          self
        end
        def empty?() Boolean end
        def fetch(key, default = nil)
          return yield key
          self[key]
        end
        def has_key?(key) Boolean end
        alias :include? :has_key?
        alias :key? :has_key?
        alias :member? :has_key?
        def has_value?(value) Boolean end
        alias :value? :has_value?
        alias :index :key
        alias :indexes :values_at
        alias :indices :values_at
        def invert() {self[nil] => key} end
        def keys() [key] end
        def length() 0 end
        def size() 0 end
        # TODO
        def merge(other) self end
        def merge!(other) self end
        def rehash() self end
        def replace(other) self end
        def shirt() [key, self[nil]] end
        def to_a() [key, self[nil]] end
        def to_hash() self end
        # TODO
        def update(other) self end
        def update(other) self end
        def values() [self[nil]] end
        def values_at() values end
      end

      class Object
        def dup() self end
        def clone() self end
        def ==(other) Boolean end
        def =~(other) Boolean end
        def eql?(other) Boolean end
        def equal?(other) Boolean end
        def is_a?(mod) Boolean end
        def kind_of?(mod) Boolean end
        def nil?() instance_of?(NilClass) end
        def respond_to?() Boolean end
        def freeze() self end
        def frozen?() Boolean end
        def taint() self end
        def untaint() self end
        def tainted?() Boolean end
        def instance_eval() end
        def hash() Fixnum end
        def to_s() '' end
        def inspect() '' end
      end

      class String
        include Comparable
        include Enumerable

        def self.new(string = nil) super() end

        def +(other) self end
        def *(times) self end
        def %(args) self end
        def <<(other) self end
        def concat(other) self end
        def =~(regexp) 0 end
        def [](nth, len = nil)
          if nth.instance_of?(String)
            self
          elsif nth.instance_of?(Regexp)
            self
          elsif nth.instance_of?(Range)
            self
          elsif len.nil?
            return 0
            return true
          else
            self
          end
        end
        def []=(nth, len, val)
          val.nil? ? len : val
        end
        def capitalize() self end
        def capitalize!() self end
        def casecmp(other, padding = nil) 0 end
        def center(width, padding = nil) self end
        def ljust(width, padding = nil) self end
        def rjust(width, padding = nil) self end
        def chomp(rs = $/) self end
        def chomp!(rs = $/) self end
        def chop() self end
        def chop!() self end
        #def clear() self end
        def count(*str) 0 end
        def crypt(salt) self end
        def delete(*str) self end
        def delete!(*str) self end
        def downcase() self end
        def downcase!() self end
        def dump() self end
        def each(rs = $/)
          yield self
          self
        end
        alias :each_line :each
        def empty?() Boolean end
        def gsub(pattern, replace = nil)
          yield self
          self
        end
        alias :gsub! :gsub
        def hex() 0 end
        def include?(substr) Boolean end
        def index(pattern, pos = 0) 0 end
        def insert(nth, other) self end
        def intern() Symbol.new end
        alias :to_sym :intern
        def length() 0 end
        alias :size :length
        def match(regexp, pos = 0) Regexp.new.match(self, pos) end
        def next() self end
        alias :next! :next
        alias :succ :next
        alias :succ! :next
        def oct() 0 end
        def replace(other) self end
        def reverse() self end
        def reverse!() self end
        def rindex(pattern, pos = 0) 0 end
        def scan(re)
          yield self
          yield [self]
          return self
          return [self]
        end
        alias :slice :[]
        alias :slice! :[]
        def split(sep = $:, limit = nil)
          result = []
          result << self
          result
        end
        def squeeze(*str) self end
        def squeeze!(*str) self end
        def strip() self end
        def strip!() self end
        def lstrip() self end
        def lstrip!() self end
        def rstrip() self end
        def rstrip!() self end
        def sub(pattern, replace = nil)
          yield self
          self
        end
        def sum() 0 end
        def swapcase() self end
        def swapcase!() self end
        def to_f() 0.0 end
        def to_i(base = nil) 0 end
        def to_s() self end
        alias :to_str :to_s
        def tr(search, replace) self end
        def tr!(search, replace) self end
        def tr_s(search, replace) self end
        def tr_s!(search, replace) self end
        def unpack(template) [] end
        def upcase() self end
        def upcase!() self end
        def upto(max)
          yield self
          self
        end
      end

      class IO
      end

      class File < IO
        module Constants
          LOCK_SH = 0
          LOCK_EX = 0
          LOCK_UN = 0
          LOCK_NB = 0
          RDONLY = 0
          WRONLY = 0
          RDWR = 0
          APPEND = 0
          CREAT = 0
          EXCL = 0
          NONBLOCK = 0
          TRUNC = 0
          NOCTTY = 0
          BINARY = 0
          SYNC = 0
          FNM_NOESCAPE = 0
          FNM_PATHNAME = 0
          FNM_PERIOD = 0
          FNM_CASEFOLD = 0
          FNM_DOTMATCH = 0
        end
      end

      class IO
        include Enumerable
        include File::Constants

        SEEK_CUR = 0
        SEEK_END = 0
        SEEK_SET = 0
        
        def self.new(fd, mode = 0)
          io = super()
          yield io
          io
        end

        def self.open(fd, mode = 0)
          io = self.new
          yield io
          io
        end

        def self.foreach(path, rs = $/)
          yield ''
          self
        end

        def self.pipe() [self.new] end

        def self.popen(command, mode = 0)
          ui = self.new
          yield io
          io
        end

        def self.read(path, length = nil, offset = nil) '' end
        def self.readlines(path, rs = $/) [''] end

        def select(reads, writes = nil, excepts = nil, timeout = nil)
          [writes, excepts, timeout]
        end

        def sysopen(path, mode = 0, perm = 0) 0 end
        def <<(object) self end
        def binmode() self end
        def close_read() nil end
        def close_write() nil end
        def closed?() Boolean end

        def each(rs = $/)
          yield ''
          self
        end

        alias :each_line :each
        def each_byte() yield 0 end
        def eof() Boolean end
        alias :eof? :eof
        def fcntl(cmd, arg = 0) 0 end
        def fsync() 0 end
        def fileno() 0 end
        alias :to_i :fileno
        def flush() self end
        def getc() 0 end
        def gets(rs = $/) '' end
        def ioctl(cmd, arg = 0) 0 end
        def isatty() Boolean end
        alias :tty? :isatty
        def lineno() 0 end
        def lineno=(number) number end
        def pi() 0 end
        def pos() 0 end
        alias :tell :pos
        def print(*arg) nil end
        def printf(format, *arg) nil end
        def putc(ch) ch end
        def puts(*obj) nil end
        def read(length = nil, outbuf = nil) '' end
        alias :readchar :getc
        alias readline :gets
        def readlines(rs = $/) [''] end
        def read_nonblock(maxlen, outbuf = nil) '' end
        def readpartial(maxlen, outbuf = nil) '' end
        def reopen(io, mode = nil) self end
        def rewind() self end
        def seek(offset, whence = SEEK_SET) 0 end
        def stat() File::Stat.new end
        def sync() Boolean end
        def sync=(newstate) newstate end
        def sysread(maxlen, outbuf = nil) '' end
        def sysseek(offset, whence = SEEK_SET) 0 end
        def syswrite(string) 0 end
        def to_io() self end
        def ungetc(char) nil end
        def write(str) 0 end
        def write_nonblock(string) 0 end
      end

      module FileTest
        def self.blockdev?(filename) Boolean end
        def self.chardev?(filename) Boolean end
        def self.executable?(filename) Boolean end
        def self.executable_real?(filename) Boolean end
        def self.exist?(filename) Boolean end
        def self.grpowned?(filename) Boolean end
        def self.directory?(filename) Boolean end
        def self.file?(filename) Boolean end
        def self.identical?(filename1, filename2) Boolean end
        def self.pipe?(filename) Boolean end
        def self.socket?(filename) Boolean end
        def self.owned?(filename) Boolean end
        def self.readable?(filename) Boolean end
        def self.readable_real?(filename) Boolean end
        def self.setuid?(filename) Boolean end
        def self.setgid?(filename) Boolean end
        def self.size(filename) 0 end
        def self.size?(filename) 0 end
        def self.sticky?(filename) Boolean end
        def self.symlink?(filename) Boolean end
        def self.writable?(filename) Boolean end
        def self.writable_real?(filename) Boolean end
        def self.zero?(filename) Boolean end
      end

      class File < IO
        class Stat
          def self.new(path) super() end

          def <=>(other) 0 end
          def ftype() '' end
          def dev() 0 end
          #def dev_major() 0 end
          #def dev_minor() 0 end
          def ino() 0 end
          def mode() 0 end
          def nlink() 0 end
          def uid() 0 end
          def gid() 0 end
          def rdev() 0 end
          #def rdev_major() 0 end
          #def rdev_minor() 0 end
          def size() 0 end
          def blksize() 0 end
          def blocks() 0 end
          def atime() Time.new end
          def mtime() Time.new end
          def ctime() Time.new() end
          def directory?() Boolean end
          def readable?() Boolean end
          def readable_real?() Boolean end
          def writable?() Boolean end
          def writable_real?() Boolean end
          def executable?() Boolean end
          def executable_real?() Boolean end
          def file?() Boolean end
          def zero?() Boolean end
          def size?()
            return 0
            false
          end
          def grpowned?() Boolean end
          def pipe?() Boolean end
          def symlink?() Boolean end
          def socket?() Boolean end
          def blockdev?() Boolean end
          def chardev?() Boolean end
          def setuid?() Boolean end
          def setgid?() Boolean end
          def sticky?() Boolean end
        end

        ALT_SEPARATOR = ''
        PATH_SEPARATOR = ''
        SEPARATOR = ''
        Separator = ''

        def self.atime(filename) Time.new end
        def self.ctime(filename) Time.new end
        def self.mtime(filename) Time.new end
        def self.basename(filename, suffix = nil) '' end
        def self.chmod(mode, *filename) 0 end
        def self.lchmod(mode, *filename) 0 end
        def self.chown(mode, group, *filename) 0 end
        def self.lchown(mode, group, *filename) 0 end
        def self.delete(*filename) 0 end
        def self.unlink(*filename) 0 end
        def self.dirname(filename) '' end
        def self.expand_path(path, default_dir = nil) '' end
        def self.extname(filename) '' end
        def self.fnmatch(pattern, path, flags = 0) Boolean end
        def self.fnmatch?(pattern, path, flags = 0) Boolean end
        def self.ftype(filename) '' end
        def self.join(*item) '' end
        def self.link(old, new) 0 end
        def self.new(path, mode = 0, perm = 0)
          file = super()
          yield file
          file
        end
        def self.open(path, mode = 0, perm = 0)
          file = self.new
          yield file
          file
        end
        def self.readlink(path) '' end
        def self.rename(from, to) 0 end
        def self.split(pathname) [''] end
        def self.stat(filename) Stat.new end
        def self.lstat(filename) Stat.new end
        def self.symlink(old, new) 0 end
        def self.truncate(path, length) 0 end
        def self.unmask(umask = 0) umask end
        def self.utime(atime, mtile, *filename) 0 end
        def self.blockdev?(filename) Boolean end
        def self.chardev?(filename) Boolean end
        def self.executable?(filename) Boolean end
        def self.executable_real?(filename) Boolean end
        def self.exist?(filename) Boolean end
        def self.grpowned?(filename) Boolean end
        def self.directory?(filename) Boolean end
        def self.file?(filename) Boolean end
        def self.identical?(filename1, filename2) Boolean end
        def self.pipe?(filename) Boolean end
        def self.socket?(filename) Boolean end
        def self.owned?(filename) Boolean end
        def self.readable?(filename) Boolean end
        def self.readable_real?(filename) Boolean end
        def self.setuid?(filename) Boolean end
        def self.setgid?(filename) Boolean end
        def self.size(filename) 0 end
        def self.size?(filename) 0 end
        def self.sticky?(filename) Boolean end
        def self.symlink?(filename) Boolean end
        def self.writable?(filename) Boolean end
        def self.writable_real?(filename) Boolean end
        def self.zero?(filename) Boolean end

        def atime() Time.new end
        def ctime() Time.new end
        def mtime() Time.new end
        def chmod(mode) 0 end
        def chown(owner, group) 0 end
        def flock(operation) 0 end
        def path() '' end
        def lstat() Stat.new end
        def truncate(length) 0 end
      end

      class Time
      end

      module Kernel
      end

      class Object
        include Kernel
      end

      BUILTINS

      # include classes as instance variables
      @cref.value.constants.each do |k, v|
        eval "@#{k}Object, @#{k} = v, v.meta"
      end

      # define native methods
      @ArrayObject.define_native_method(:new) do
        # TODO
        make_typed_array_type([])
      end

      @Array.define_native_method(:<<, :value) do
        # TODO clear templates
        value = local_var_type(:value)
        @self.elem_type_var << value if value
        #propagate(@self)
        @self
      end

      @Array.define_native_method(:[]) do
        ElementVertex.new(@self.elem_type_var)
      end

      @HashObject.define_native_method(:new) do
        # TODO
        make_typed_hash_type({})
      end

      @Hash.define_native_method(:each) do
        if @given_block
          do_yield([ElementVertex.new(@self.key_type_var), ElementVertex.new(@self.value_type_var)])
        end
        @self
      end

      @Hash.define_native_method(:[]) do
        ElementVertex.new(@self.value_type_var)
      end

      @Hash.define_native_method(:[]=, :key, :value) do
        # TODO clear templates
        key = local_var_type(:key)
        value = local_var_type(:value)
        if key and value
          @self.key_type_var << key
          @self.value_type_var << value
          #propagate(@self)
        end
        @self
      end

      @Hash.define_native_method(:key) do
        ElementVertex.new(@self.key_type_var)
      end

      @Kernel.define_native_method(:require, :feature) do
        if @current_method_arg_vertecies
          feature = @current_method_arg_vertecies[0]
          if feature[1].instance_of?(String)
            do_load(feature[1])
          end
        end
        nil
      end

      @Kernel.define_native_method(:load, :file) do
        if @current_method_arg_vertecies
          file = @current_method_arg_vertecies[0]
          if file[1].instance_of?(String)
            do_load(file[1])
          end
        end
        nil
      end

      # define boolean type for convenience
      @Boolean = Vertex.new(nil)
      @Boolean.type_var << @TrueClass
      @Boolean.type_var << @FalseClass
      @cref.value.constants[:Boolean] = @Boolean
    end

    def do_load(file)
      unless @features[file]
        @features[file] = true
        path = File.file?(file) ? file : find(file)
        @features[file] = infer(open(path, 'rb').read) if path
      end
    end

    def cartesian_product(arrays)
      size = arrays.inject(1) {|r, a| r *= a.size}
      return [] if size == 0
      unit = size
      results = Array.new(size) {Array.new(arrays.size)}
      arrays.each_with_index do |array, i|
        k = 0
        c = 0
        n = array.size
        new_unit = unit / n
        0.upto(size - 1) do |j|
          results[j][i] = array[c]
          j += 1
          k += 1
          if k == new_unit
            k = 0
            c += 1
            c = 0 if c == n
          end
        end
        unit = new_unit
      end
      results
    end

    def dump
      puts 'Local Variables:'
      @scope.local_vars.each do |k, v|
        puts "    #{k}	=	#{v.type_var.inspect}"
      end
    end
  end
end

if __FILE__ == $0
  inf = RSense::Inferrer.new
  puts 'AST:'
  pp(inf.infer(ARGF.read))
  puts
  inf.dump
end
